package practice.tmp;

import java.util.List;

public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int i, int j) {
        if (i > j) return null;
        if (i == j) return lists[i];
        int mid = (i + j) >> 1;
        ListNode A = merge(lists, i, mid);
        ListNode B = merge(lists, mid + 1, j);
        return merge2Lists(A, B);
    }

    public ListNode merge2Lists(ListNode A, ListNode B) {
        if (A == null) return B;
        if (B == null) return A;
        if (A.val < B.val) {
            A.next = merge2Lists(A.next, B);
            return A;
        } else {
            B.next = merge2Lists(A, B.next);
            return B;
        }
    }
}
